package com.cqs.leetcode;

/**
 * 讲1 2....10 11... 看成一个字符串 求第N个字符串对应的数字
 */
public class NthDigit {

    /**
     * 1bit 1-----9  1×9个
     * 2bit 10----99 2×（100-10）个
     * 3bit 100----999 3×（1000-100）个
     * 4bit 1000----9999 4×（10000-1000）个
     * ....
     * m bit 1.... 99...99 m ×（10^m - 10^(m-1)）个
     *
     * @param n
     * @return
     */
    public int findNthDigit(int n) {
//        System.out.print("n: " + n);
        int sum = 0;
        int bits = 1;
        while ((sum + bits * (Math.pow(10, bits) - Math.pow(10, bits - 1))) < n) {
            sum += bits * (Math.pow(10, bits) - Math.pow(10, bits - 1));
            bits++;
        }
        n -= sum;
        int it = n / bits;
        int md = n % bits;

        int cur = (int) Math.pow(10, bits - 1);
        cur += it;
        if (md == 0) {
            cur -= 1;
            md = bits;
        }
        int result = 0;
        while ((bits - md) >= 0) {
            result = cur % 10;
            cur = cur / 10;
            ++md;
        }
        return result;
    }


    //--leetcode
    public int findNthDigit2(int n) {
        long len = 1;
        long count = 9;
        long start = 1;
        while (n > len * count) {
            n -= len * count;
            start *= 10;
            count *= 10;
            len += 1;
        }
        //数字转化为字符串 方便求制定位置的数字
        String s = (start += (n - 1) / len) + "";
        return (int) s.charAt((int) ((n - 1) % len)) - 48;
    }


    public static void main(String[] args) {
        NthDigit digit = new NthDigit();
//        for (int i = 1; i < 20000; i++) {
//            System.out.print(digit.findNthDigit(i) + "\t");
//            if ((i + 1) % 10 == 0) {
//                System.out.println();
//            }
//        }
        System.out.println(digit.findNthDigit(Integer.MAX_VALUE));
        System.out.println(digit.findNthDigit2(Integer.MAX_VALUE));
    }
}
